The present invention relates to a method and apparatus for determining the Error Correction Code (ECC) failure rate or probability of iterative decoding algorithms. The invention further relates to a program of instructions (e.g., software) for implementing the method.
The performance of digital communication and storage systems can be significantly improved by the use of error correction coding. As a result, most, if not all, such systems use some form of error correction coding, which generally involves systematically adding redundant bits to each block of data as insurance against read/write errors. A given ECC can recover the original data from a contaminated block if the number of erroneous bits is less than the maximum number allowed by that particular code.
In the magnetic recording industry, different error correction coding and detection schemes are compared against each other by considering both the bit error rate (BER) versus signal-to-noise (SNR) curves and the ECC failure probability. The BER provides useful information as to the frequency of errors. However, since the data is encoded using an ECC, the true goal is to minimize the ECC failure probability rather than the BER itself. Therefore, one needs to compare not only the frequency of errors (which is reflected by the BER) but also the types and magnitudes of errors that occur. If scheme A has fewer errors overall than scheme B, but the probability of a large error burst is higher for A than for B, then the ECC failure rate may be higher for A than for B.
For systems in which an output BER below 10xe2x88x9210 is desirable, ECCs, such as Reed-Solomon (RS) codes, are usually concatenated with convolutional codes. In recent years, convolutional codes have been replaced by iterative codes to deliver the required BER. Since an iterative decoding algorithm is required to decode such iterative codes, the failure probability of the ECC is based on the error characteristics of the decoding algorithm. While iterative codes such as turbo codes and low-density parity-check (LDPC) codes have shown very good performance for communication systems at output BERs of 10xe2x88x923 to 10xe2x88x927, performance is much less certain at output BERs below 10xe2x88x9210. Moreover, bit-by-bit simulation of systems with an output BER below 10xe2x88x9210 is difficult due to the fact that the number of bits that need to be processed is too large.
Due to such difficulty, the ECC failure probability of iterative decoding algorithms are typically not known until after the integrated circuit implementing the decoding algorithm has been fabricated. Having to construct the decoding circuit before the effectiveness of the underlying decoding algorithm is known can be both time-consuming and costly.
It is therefore an object of this invention to overcome the above-mentioned problems.
It is another object of this invention to provide a design-based tool capable of estimating ECC failure probabilities in the BER range below 10xe2x88x9210 of iterative decoding algorithms to determine the ECC failure performance of a particular algorithm by modeling it before the circuit implementing the algorithm is fabricated.
It is a further object of this invention to provide a program of instructions embodied on a device-readable medium for implementing such a design-based tool.
According to one aspect of the invention, a method is provided for determining error correction code failure probability of an iterative decoding algorithm for a pre-selected range of signal-to-noise ratio values and a pre-selected interleaved error correction code. The method comprises the steps of: determining a signal-to-noise ratio value range where a bit error rate of the iterative decoding algorithm with respect to signal-to-noise ratio defines an error floor region; determining a probability Pdmin of a minimal distance error event occurring in the decoding algorithm for at least one signal-to-noise ratio value within the previously-determined signal-to-noise ratio value range; determining probability wi that a minimal distance error event corrupts i bytes in the same interleave of the pre-selected error correction code; and determining the error correction code failure probability for the signal-to-noise ratio value range determined in step (a) based on the previously determined probabilities Pdmin and wi.
In addition to defining an error floor region, the bit error rate of the iterative decoding algorithm with respect to signal-to-noise ratio further defines a steep drop region and a transitional region, where the signal-to-noise ratio value range of the error floor region is greater than a signal-to-noise ratio value range of the transitional region which is greater than a signal-to-noise ratio value range of the steep drop region.
Preferably, the step of determining Pdmin comprises determining a probability Pdmin of a minimal distance error event occurring in the decoding algorithm for a plurality of signal-to-noise ratio values within the previously-determined signal-to-noise ratio value range. This determining step also preferably comprises determining a minimum Hamming weight of error events of the decoding algorithm dmin and multiplying the probability Pdmin by dmin.
Another aspect of the invention involves an apparatus for determining error correction code failure probability of an iterative decoding algorithm for a pre-selected range of signal-to-noise ratio values and a pre-selected interleaved error correction code. The apparatus comprises various circuits for implementing the functions described above. These circuits may be physically distinct integrated circuits, or they may be embodied as a single integrated circuit.
In accordance with another aspect, the invention provides a device-readable medium embodying a program of instructions for execution by a device, such as a computer processor, for performing a method of determining error correction code failure probability of an iterative decoding algorithm for a pre-selected range of signal-to-noise ratio values and a pre-selected interleaved error correction code. The program of instructions comprises instructions for carrying out the steps of the above-described method.
Other objects and attainments together with a fuller understanding of the invention will become apparent and appreciated by referring to the following description and claims taken in conjunction with the accompanying drawings.